BZOJ1096【ZJOI2007】仓库建设 <斜率优化>

Problem

【ZJOI2007】仓库建设

Description

公司有个工厂，由高到底分布在一座山上。如图所示，工厂在山顶，工厂在山脚。由于这座山处于高原内陆地区（干燥少雨），公司一般把产品直接堆放在露天，以节省费用。突然有一天，公司的总裁先生接到气象部门的电话，被告知三天之后将有一场暴雨，于是先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。由于地形的不同，在不同工厂建立仓库的费用可能是不同的。第个工厂目前已有成品件，在第个工厂位置建立仓库的费用是。对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，而由于公司产品的对外销售处设置在山脚的工厂，故产品只能往山下运（即只能运往编号更大的工厂的仓库），当然运送产品也是需要费用的，假设一件产品运送个单位距离的费用是。假设建立的仓库容量都都是足够大的，可以容下所有的产品。你将得到以下数据：

1. 工厂距离工厂的距离（其中）
2. 工厂目前已有成品数量
3. 在工厂建立仓库的费用

请你帮助公司寻找一个仓库建设的方案，使得总的费用（）最小。

Input

第一行包含一个整数，表示工厂的个数。接下来行每行包含两个整数, 意义如题中所述。

Output

仅包含一个整数，为可以找到最优方案的费用。

Sample Input

3
0 5 10
5 3 100
9 6 10

Sample Output

32

标签：斜率优化DP

Solution

由题意，易得到方程：
那么对于当前到的位置，一定存在使得


按照此斜率维护单调栈即可。

Code

#include <bits/stdc++.h>
#define MAX_N 1000000
using namespace std;
typedef double dnt;
typedef long long lnt;
template <class T>
inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, c[MAX_N+5], x[MAX_N+5], m[MAX_N+5];
lnt s1[MAX_N+5], s2[MAX_N+5], f[MAX_N+5];	int l, r, sta[MAX_N+5];
dnt calc(int p, int q) {return (dnt)(f[p]-f[q]+s1[p]-s1[q])/(dnt)(s2[p]-s2[q]);}
int main() {
    read(n);
    for (int i = 1; i <= n; i++) read(x[i]), read(m[i]), read(c[i]);
    for (int i = 1; i <= n; i++) s1[i] = s1[i-1]+1LL*m[i]*x[i], s2[i] = s2[i-1]+m[i];
    for (int i = 1; i <= n; i++) {
        while (l < r && calc(sta[l+1], sta[l]) <= x[i]) l++;
        f[i] = f[sta[l]]+1LL*x[i]*(s2[i]-s2[sta[l]])-s1[i]+s1[sta[l]]+c[i];
        while (l < r && calc(sta[r], sta[r-1]) > calc(i, sta[r])) r--;
        sta[++r] = i;
    }
    return printf("%lld", f[n]), 0;
}